import copy
import time 

from util import Queue

class Colors:
    RED = '\033[91m'
    GREEN = '\033[92m'
    BLUE = '\033[94m'
    YELLOW = '\033[93m'
    PURPLE = '\033[95m'
    CYAN = '\033[96m'
    GRAY = '\033[90m'
    ENDC = '\033[0m'
    
    beautify = {
        '': ' ',
        'R': RED + 'O' + ENDC,
        'G': GREEN + 'O' + ENDC,
        'B': BLUE + 'O' + ENDC,
        'Y': YELLOW + 'O' + ENDC,
        'R1': RED + 'O' + ENDC,
        'G1': GREEN + 'O' + ENDC,
        'B1': BLUE + 'O' + ENDC,
        'Y1': YELLOW + 'O' + ENDC,
        'R2': RED + 'O' + ENDC,
        'G2': GREEN + 'O' + ENDC,
        'B2': BLUE + 'O' + ENDC,
        'Y2': YELLOW + 'O' + ENDC,
        'rn': RED + '^' + ENDC,
        're': RED + '<' + ENDC,
        'rs': RED + '^' + ENDC,
        'rw': RED + '>' + ENDC,
        'gn': GREEN + 'v' + ENDC,
        'ge': GREEN + '<' + ENDC,
        'gs': GREEN + '^' + ENDC,
        'gw': GREEN + '>' + ENDC,
        'bn': BLUE + 'v' + ENDC,
        'be': BLUE + '<' + ENDC,
        'bs': BLUE + '^' + ENDC,
        'bw': BLUE + '>' + ENDC,
        'yn': YELLOW + 'v' + ENDC,
        'ye': YELLOW + '<' + ENDC,
        'ys': YELLOW + '^' + ENDC,
        'yw': YELLOW + '>' + ENDC,
        '*': '*',
        'X': 'X',
        'T1': PURPLE + 'T' + ENDC,
        'T2': CYAN + 'T' + ENDC,
        'T3': GRAY + 'T' + ENDC,
    }

"""
Encoding:
R/G/B/Y = Red/Green/Blue/Yellow goop
r/g/b/y = Red/Green/Blue/Yellow gate
n/s/e/w = North/South/East/West facing gate
 /*/X/T = Empty/Box/Hole/Teleporter grid square
1/2/3 = Numbers to identify teleporters of the same color
"""
class Board(object):
    def __init__(self, rows):
        self.level_number = rows[0][0]  # First row has the level number. Something like "3.7".
        self.board = rows[1:]  # Other rows correspond to board rows. 8 columns each.
        self.height = len(self.board)
        self.width = len(self.board[0])
        self.teleporters = {}  # Maps each teleporter to its spouse.
        self.goops = {}  # Maps goop location to its color. e.g., (6, 0) -> RED.
        for i, row in enumerate(self.board):
            for j, cell in enumerate(row):
                if Board.isGoop(cell):
                    self.goops[(i, j)] = cell
                    self.board[i][j] = '' # Erase goops from board... use goops{} exclusively
                if Board.isTeleporter(cell):
                    # This is tricky but makes things elegant.
                    if cell not in self.teleporters:  # First teleporter of the couple.
                        self.teleporters[cell] = (i, j)
                    else:  # This is the second teleporter. Map each of the two to the other one.
                        self.teleporters[(i, j)] = self.teleporters[cell]
                        self.teleporters[self.teleporters[cell]] = (i, j)
                        del self.teleporters[cell]  # Delete the mapping for 'T1' or whatsover.
                        # The tricky part is that we use the map at first for storing something like
                        # 'T1' -> (3, 2), and then when we find the other teleporter, say at (6, 1),
                        # we remove this mapping and add two mappings: (3, 2) -> (6, 1), (6, 1) -> (3, 2).

    @staticmethod
    def isGoop(cell):
        return cell and cell[0] in ['R', 'G', 'B', 'Y']

    @staticmethod
    def isTeleporter(cell):
        return cell.startswith('T')
    
    @staticmethod
    def isHole(cell):
        return cell == 'X'
    
    # e.g., "rs" means a red gate facing south.
    @staticmethod
    def isGate(cell):
        return cell[0] in ['r', 'g', 'b', 'y'] and cell[1] in ['n', 'e', 's', 'w']
    
    # 'R' means red goop, while 'rs' means red gate (facing south).
    @staticmethod
    def sameColor(goop, gate):
        return gate[0] == goop[0].lower()
    
    @staticmethod
    def canEnter(direction, gate):
        # Goop must be moving in the opposite direction that the gate is facing to enter it.
        opposite = {(-1, 0): 's',
                    (0, +1): 'w',
                    (+1, 0): 'n',
                    (0, -1): 'e'}
        return opposite[direction] == gate[1]
    
    @staticmethod
    def inBoard(board, row, col):
        return row >= 0 and row < len(board) and col >= 0 and col < len(board[0])

    def getApplicableActions(self):
        actions = []
        for i, j in self.goops:
            for delta_i, delta_j in [(-1, 0),  # North
                                     (0, +1),  # East
                                     (+1, 0),  # South
                                     (0, -1),  # West 
                                    ]:
                k, l = i, j
                while True:  # The outer loop is to enable teleporting.
                    # Keep moving until you hit a wall/something.
                    k += delta_i
                    l += delta_j


                    while Board.inBoard(self.board, k, l) and not self.board[k][l] and ((k,l) not in self.goops):
                        # We're still on the board, didn't hit a anything static or any goop.
                        # modified for goop check without using board -Max
                        k += delta_i
                        l += delta_j

                    if Board.inBoard(self.board, k, l) and Board.isTeleporter(self.board[k][l]):  # Hit a teleporter. Jump.
                        k, l = self.teleporters[(k, l)]
                    else:
                        break

                # If you hit a black hole, then this direction isn't applicable.
                if Board.inBoard(self.board, k, l) and Board.isHole(self.board[k][l]):
                    continue
                
                # If you hit your gate, disappear.
                # Modified to use goops rather than board for goop position -Max
               
                if (k,l) not in self.goops and (Board.inBoard(self.board, k, l) and 
                                                Board.isGate(self.board[k][l]) and 
                    Board.sameColor(self.goops[(i,j)], self.board[k][l]) and 
                    Board.canEnter((delta_i, delta_j), self.board[k][l])):
                    actions.append(((i, j), (-1, -1)))
                    continue
                # Otherwise, hit a wall, a block, another goop, or the wrong gate, stop before that.
                # Unless that's where you are! (Couldn't move.) Also, if you got stuck in the middle
                # of a teleporter, ignore this action.
                new_i, new_j = k - delta_i, l - delta_j
                if (new_i, new_j) != (i, j) and not Board.isTeleporter(self.board[new_i][new_j]):
                    actions.append(((i, j), (new_i, new_j)))
        return actions

    # Moves the goop from (i, j) -> (k, l).
    # modified to use goops instead of board -Max
    def applyAction(self, ((i, j), (k, l))):
        if (k, l) != (-1, -1):  # (-1, -1) means that the goop is gone (entered its gate).
            #self.board[k][l] = self.board[i][j]
            self.goops[(k, l)] = self.goops[(i, j)]
        
        #self.board[i][j] = ''
        del self.goops[(i, j)]
        
    @staticmethod
    def _reachedGoal(relaxedGoops):
        for goopLocations in relaxedGoops.values():
            if (-1, -1) not in goopLocations:
                return False
        return True
    
    def getHrpg(self):
        #from landmark import LandMark
        relaxedGoops = {goop: {loc: (None, None)} for loc, goop in self.goops.items()} 
        #rG = LandMark(relaxedGoops, state)
        rG = None
        staticBoard = copy.deepcopy(self.board)
        for i, j in self.goops:
            staticBoard[i][j] = ''
        
        changed = True
        iteration = 0 
        #print iteration, changed, relaxedGoops
        while changed and not Board._reachedGoal(relaxedGoops):
            iteration += 1
            rG, relaxedGoops, changed = Board._relaxGoops(rG, iteration, staticBoard, self.teleporters, relaxedGoops)
            #print iteration, changed, relaxedGoops
        
        if not Board._reachedGoal(relaxedGoops):
            return -1  # Goal is not reachable from given state!
        
        #print relaxedGoops
        '''for goop in relaxedGoops:
            print "goop ", goop
            print "dict ", relaxedGoops[goop]
            for location in relaxedGoops[goop]:
                print "location ", location, " from ", relaxedGoops[goop][location]  
        '''
        requiredActions = set()  # (goop, (i, j), (k, l)) means move goop from (i, j) to (k, l).
        openGoals = Queue()
        for goop in relaxedGoops:
            openGoals.push((goop, (-1, -1)))
        while not openGoals.isEmpty():
            #print openGoals.list
            goop, loc = openGoals.pop()
            previousLoc, preCondition = relaxedGoops[goop][loc]
            #print "previousLoc ",  previousLoc, " preCondition ", preCondition
            if previousLoc:
                openGoals.push((goop, previousLoc))
                requiredActions.add((goop, (previousLoc, loc)))
            if preCondition:
                otherGoop, otherGoopLoc = preCondition
                openGoals.push((otherGoop, otherGoopLoc))
        return len(requiredActions)


    @staticmethod
    def _findGoopInLoc(movingGoop, relaxedGoops, loc):
        """
        Finds a goop that is different from the given movingGoop, and can be located at the given 
        location and returns it. If no such goop exists, returns None.
        """
        for goop, goopLocations in relaxedGoops.items():
            if goop != movingGoop and loc in goopLocations:
                return goop
        return None

    @staticmethod
    def _relaxGoops(rG, iteration, staticBoard, teleporters, relaxedGoops):
        """
        
        Returns true if the returned newRelaxedGoops is different from relaxedGoops. i.e., some 
        relaxed action was added. False otherwise.
        This way the return value could be used to know when to stop relaxing.
        Similarly to the lecture where we stop at the k'th iteration when A[k-1] == A[k].
        """
        changed = False
        newRelaxedGoops = copy.deepcopy(relaxedGoops)

        #print relaxedGoops.items()
        for goop, goopLocations in relaxedGoops.items():
            #print goop, goopLocations
            #time.sleep(10)
            for i, j in goopLocations:
                loc = (i, j)
                if loc == (-1, -1):
                    continue
                for delta_i, delta_j in [(-1, 0),  # North
                                         (0, +1),  # East
                                         (+1, 0),  # South
                                         (0, -1),  # West
                                        ]:
                    k, l = i, j
                    while True:  # The outer loop is to enable teleporting.
                        # Keep moving until you hit a wall/something.
                        k += delta_i
                        l += delta_j

                        if not Board.inBoard(staticBoard, k, l):
                            break
                        
                        blockingGoop = Board._findGoopInLoc(goop, relaxedGoops, (k, l))
                        if blockingGoop != None:
                            # Add action
                            new_i, new_j = k - delta_i, l - delta_j
                            newLoc = (new_i, new_j)
                            
                            if (newLoc != loc and not Board.isTeleporter(staticBoard[new_i][new_j])):
                                if newLoc in newRelaxedGoops[goop] and rG != None:
                                    #pass
                                    rG.put(iteration, goop, newLoc, loc, (blockingGoop, (k, l)))
                                    #print "The location with multiple preconditions is ", newLoc 
                                    #print "Old precondition was :", newRelaxedGoops[goop][newLoc]
                                    #print "The alternate precondition is :", (loc, (blockingGoop, (k, l)))
                            if (newLoc != loc and not Board.isTeleporter(staticBoard[new_i][new_j]) 
                                                            and not newLoc in newRelaxedGoops[goop]):
                                newRelaxedGoops[goop][newLoc] = (loc, (blockingGoop, (k, l)))
                                if rG != None: rG.put(iteration, goop, newLoc, loc, (blockingGoop, (k, l)))
                                changed = True
                            continue

                        if not staticBoard[k][l]:
                            # We're still on the board, didn't hit a anything static or any goop.
                            continue
                                
                        if Board.isTeleporter(staticBoard[k][l]):  # Hit a teleporter. Jump.
                            k, l = teleporters[(k, l)]
                            continue
                        
                        break  # Hit something that's not a teleporter or goop.
    
                    # If you hit a black hole, then this direction isn't applicable.
                    if Board.inBoard(staticBoard, k, l) and Board.isHole(staticBoard[k][l]):
                        continue

                    # If you hit your gate, can disappear.
                    if (Board.inBoard(staticBoard, k, l) and Board.isGate(staticBoard[k][l]) and 
                        Board.sameColor(goop, staticBoard[k][l]) and 
                        Board.canEnter((delta_i, delta_j), staticBoard[k][l])):
                        if (not (-1, -1) in newRelaxedGoops[goop]):
                            newRelaxedGoops[goop][(-1, -1)] = (loc, None)
                            if rG != None: rG.put(iteration, goop, (-1, -1), loc, None)
                            changed = True
                        else:
                            if rG !=None: rG.put(iteration, goop, (-1, -1), loc, None)
                        continue
                    
                    # Otherwise, hit a wall, a block, another goop, or the wrong gate, stop before that.
                    # Unless that's where you are! (Couldn't move.) Also, if you got stuck in the middle
                    # of a teleporter, ignore this action.
                    new_i, new_j = k - delta_i, l - delta_j
                    newLoc = (new_i, new_j)
                    if newLoc != loc and not Board.isTeleporter(staticBoard[new_i][new_j]) and not newLoc in newRelaxedGoops[goop]:
                        newRelaxedGoops[goop][newLoc] = (loc, None)
                        if rG != None: rG.put(iteration, goop, newLoc, loc, None)
                        changed = True
        if rG != None: rG.update()
        return rG, newRelaxedGoops, changed

    def getNextState(self, action):
        nextState = self.copy()
#         print nextState.goops, self.goops, action
        nextState.applyAction(action)
#         print nextState.goops, self.goops, action
        return nextState
    
    def getNextStates(self):
        nextStates = []
        for action in self.getApplicableActions():
            nextState = self.copy()
            nextState.applyAction(action)
            nextStates.append(nextState)
        return nextStates
    
    def isGoal(self):
        return len(self.goops) == 0
    
    def copy(self):
        cls = self.__class__
        newstate = cls.__new__(cls)
        newstate.__dict__ = self.__dict__.copy()
        setattr(newstate,'goops',self.goops.copy())
        return  newstate


    # modified to re-add and remove goops using goops dict instead of from board 
    def __repr__(self):
        s = 'Level %s\n' % self.level_number
        s += 19 * '-' + '\n' 
        for (i,j) in self.goops:
            self.board[i][j] = self.goops[(i,j)]
        for row in self.board:
            s += '| '
            for col in row:
                s += Colors.beautify[col] + ' '
            s += '|\n'
        s += 19 * '-' + '\n'
        s += 'Goops: %r\n' % self.goops
        s += 'Teleporters: %r' % self.teleporters
        for (i,j) in self.goops:
            self.board[i][j] = ''
        
        #s += 'Hrpg = %r' % self.getHrpg()
        return s
    
    def key(self):
        return tuple(sorted(self.goops.items()))
    
    def __eq__(x, y):
        return x.key() == y.key()
    
    def __hash__(self):
        return hash(self.key())
        
    def getHOrderLM(self, state):
        """
        Uses a relaxed planning graph to estimate sub goals that need to be accomplished before
        goal state can be reached.  The return type is a queue
        """
        from landmark import LandMark
        relaxedGoops = {goop: {loc: (None, None)} for loc, goop in self.goops.items()} 
        landM = LandMark(relaxedGoops, state)
        staticBoard = copy.deepcopy(self.board)
        for i, j in self.goops:
            staticBoard[i][j] = ''
        
        changed = True
        iteration = 0 
        while changed and not Board._reachedGoal(relaxedGoops):
            iteration += 1
            landM, relaxedGoops, changed = Board._relaxGoops(landM, iteration, staticBoard, self.teleporters, relaxedGoops)
        if not Board._reachedGoal(relaxedGoops):
            return -1  # Goal is not reachable from given state!
        landMarkGraph, landMarkLeaves = landM.getLandMarks(copy.deepcopy(self.goops), str(self.level_number))
        #print subGoals.list
        return landMarkGraph, landMarkLeaves
